「問：n個の要素からなる集合の部分集合は全部で2^n個あることを示せ hatoriさんヒント」の読解
恐らく"サブクエスト"に時間がかかりすぎるのは不本意だと思うので、なるべくcFQ2f7LRuLYP.iconさんのやろうとしている方法に従いつつ解答(の一歩手前)を考えてみましたhatori.icon
（注意：これが唯一の証明方法あるいは最も簡単な証明方法というわけではありません。たぶん）
他にも証明方法があるらしいcFQ2f7LRuLYP.icon
そんな感じですhatori.icon
用語の定義１：与えられた集合$ Aの部分集合全体を$ \mathfrak{P}(A)と表し、$ Aの冪集合と呼ぶ $ \mathfrak{P}(A)は集合の集合です $ \mathfrak{P}はPower setの頭文字Pのフラクトゥール 冪集合（べきしゅうごう、英: power set）とは、数学において、与えられた集合から、その部分集合の全体として新たに作り出される集合のことである。べきは冪乗の冪（べき）と同じもので、冪集合と書くのが正確だが、一部分をとった略字として巾集合とも書かれる。
うーむ…
例だ、例を出すんだ…
集合Aがあるとする
$ A=\{1,2\}
Aの部分集合の全体は以下
$ \{\},\{1\},\{2\},\{1,2\}
これを全体として新しく作り出される集合を冪集合という
カッコの中をどう書くか？
$ A=\{a,b\} のべき集合は
$ 2^A = \Bigl\{ \emptyset, \{a\}, \{b\}, \{a,b\}\Bigr\}
である。
なるほどcFQ2f7LRuLYP.icon
$ \mathfrak{P}(A)=\{\emptyset,\{1\},\{2\},\{1,2\}\}
では集合Bがあるとしてその冪集合$ \mathfrak{P}(B)はどうなるか？
$ B=\{0,1,2\}
Bの部分集合は
$ \emptyset,\{0\},\{1\},\{2\},\{0,1\},\{1,2\},\{0,2\},\{0,1,2\}
8つ
$ \mathfrak{P}(B)=\{\emptyset,\{0\},\{1\},\{2\},\{0,1\},\{1,2\},\{0,2\},\{0,1,2\}\}
用語の定義２：有限集合$ Aの要素の個数を$ |A|と表す（無限集合の場合は要素の個数ではなく濃度という） $ \#Aや$ \mathrm{card}(A)とも表す
例
$ A=\{1,2\}のとき、$ |A|=2
$ B=\{0,1,2\}のとき、$ |B|=3
$ \mathfrak{P}(A)は？
$ \mathfrak{P}(A)=\{\emptyset,\{1\},\{2\},\{1,2\}\}
要素は4つ
$ |\mathfrak{P}(A)|=4
では$ \mathfrak{P}(B)の場合は？
$ \mathfrak{P}(B)=\{\emptyset,\{0\},\{1\},\{2\},\{0,1\},\{1,2\},\{0,2\},\{0,1,2\}\}
$ |\mathfrak{P}(B)|=8
ここもよし
用語の定義３：集合$ Aと$ Bが共通部分を持たないとき、和集合$ A\cup Bを$ Aと$ Bの(集合論的)直和あるいは非交和とよぶ（このとき特に記号を変えて$ A\sqcup Bとも書く） 互いに素 (集合)←(集合)なんてつけてたっけ？
「互いに素」という用語は整数に関するある主張を意味することが多いので、それと区別したかったのではないかと思いますhatori.icon 二つの整数 a, b が互いに素（たがいにそ、英: coprime, relatively prime, prime to）であるとは、a, b を共に割り切る正の整数が 1 のみであることをいう。このことは a, b の最大公約数 gcd(a, b) が 1 であることと同値である。 ﾌﾑｰcFQ2f7LRuLYP.icon
https://gyazo.com/424786f540f741c1f358ddd31edbefcf
AとBは共通部分を持たない
このときの和集合$ A\cup Bを$ Aと$ Bの(集合論的)直和あるいは非交和とよぶ（このとき特に記号を変えて$ A\sqcup Bとも書く） ここまで用語の定義
$ X_{3}=\{1,2,3\}における例
いま$ X_{3}=\{1,2,3\}とおき、$ |\mathfrak{P}(X_{3})|=2^{3}となることを示します
はいcFQ2f7LRuLYP.icon
要素の個数で分類する。はいcFQ2f7LRuLYP.icon
0個、1個、2個、3個の4つに分類するんだな
0個の場合
$ |A|=0の場合：$ A = \emptyset
$ |A|の個数が0なら、$ A=\emptyset
$ \{\}空集合
どうでもいいけど$ \emptysetをemptyって表現するのぴったりだな(?) 空家事件(The Empty House)思い出す
3つの相異なるものから何も選ばない方法は$ {}_{3}\mathrm{C}_{0}通り
はい
順列を出して考えるんだったな
$ _{n}\mathrm{C}_{m}=\frac{_{n}\mathrm{P}_{m}}{_{m}\mathrm{P}_{m}}
$ {}_{n}\mathrm{P}_{m}=n\times(n-1)\times\cdots\times(n-m+1)=\frac{n!}{(n-m)!}
今回は$ {}_{3}\mathrm{C}_{0}なので
$ _{3}\mathrm{C}_{0}=\frac{_{3}\mathrm{P}_{0}}{_{0}\mathrm{P}_{0}}
$ 0!=1
ここが掴めてないんだなー
0個選ぶっていうのが現実の事項と結びついてしまってる
$ _{3}\mathrm{P}_{0}ってどうやって計算するの？？となっている
$ _{3}\mathrm{P}_{1}ならわかる
$ _{3}\mathrm{P}_{1}=\frac{3!}{(3-1)!}=\frac{3!}{2!}=\frac{3\times2}{2\times1}=3
おっと？それなら
$ _{3}\mathrm{P}_{0}=\frac{3!}{(3-0)!}=\frac{3!}{3!}=\frac{3\times2\times1}{3\times2\times1}=1
ということは
$ _{0}\mathrm{P}_{0}=\frac{0!}{(0-0)!}=\frac{0!}{0!}=\frac{1}{1}=1
できた！
$ _{3}\mathrm{C}_{0}=\frac{_{3}\mathrm{P}_{0}}{_{0}\mathrm{P}_{0}}=\frac{1}{1}=1
1通りだ！
よって$ |\{A\in\mathfrak{P}(X_{3}) ; |A|=0\}|={}_{3}\mathrm{C}_{0}
ここのコロン;の使い方は一体…？
これまだ出てないんだよな……
突如ポップしたサブクエストをクリアするためのヒントを解くための鍵がメインクエストにあることがわかった
そうでもなかったcFQ2f7LRuLYP.icon
回帰した
この;は単なる区切りのつもりで使っているので、数学的な意味はないですhatori.icon
記号が紛らわしくてすみません
集合の中では|、\midあるいは:を使って区切るのが正当な記法だと思います
ありがとうございます～cFQ2f7LRuLYP.icon
$ \landじゃだめなんかなyosider.icon
こっちのほうが情報がある気がする
これでも意味は通りますが、あまり見かけない書き方かも...hatori.icon
$ \{a\in A|P(a)\}:=\{a|a\in A\land P(a)\}だから、$ \{a\in A\land P(a)\}だと意味が通らなそうtakker.icon
一つの論理式$ Q:\iff a\in A\land P(a)を元とする集合$ \{Q\}と誤解されかねない
たし🦀hatori.icon
「意味は通る」＝「多少表記が不正確だけれど、それは私の脳内で適当に修正可能であり言わんとすることは分かります」というニュアンスで書いていた
じゃあもどって…
$ |\{A\in\mathfrak{P}(X_{3}) ; |A|=0\}|={}_{3}\mathrm{C}_{0}
$ |A|は有限集合$ Aの要素の個数
用語の定義2を参照
その中に$ \{A\in\mathfrak{P}(X_{3}) ; |A|=0\}が入ってる
(しばらく更新が無かったので、要らないかもしれませんが助け舟(?)を出しますhatori.icon)
助け舟ありがとうございます！cFQ2f7LRuLYP.icon
本編の方に戻ってうろうろしてました
突如スン…となって別の方で遊んでいることが多く、申し訳無いですcFQ2f7LRuLYP.icon
;が内包記法の|と同じ役割をしているという理解はしています
したがって$ |\{A\in\mathfrak{P}(X_{3}) ; |A|=0\}|=|\{\emptyset\}|=1={}_{3}\mathrm{C}_{0} \; \cdots \clubsuit
ちょっと脱線しますが「3つの相異なるものから何も選ばない方法は$ {}_{3}\mathrm{C}_{0}通り」という文は、あくまで上式$ \clubsuitの解釈のひとつです
次のように解釈し直せばより日常的な感覚に近いため、腑に落ちるかもしれません
「取り出すものを選ぶ＝取り出さないものを選ぶ」という発想の転換から、今の場合「3つの相異なるものから取り出さないものを3つ選ぶ方法は$ {}_{3}\mathrm{C}_{3}通り」と考えても正しい値が得られます この解釈で一般に$ {}_{n}\mathrm{C}_{r}={}_{n}\mathrm{C}_{n-r}となることも示せます（階乗で表せば自明ですが）
$ |A|=1の場合：$ A \in \{\{1\},\{2\},\{3\}\}
3つの相異なるものから1つのものを選ぶ方法は$ {}_{3}\mathrm{C}_{1}通り
よって$ |\{A\in\mathfrak{P}(X_{3}) ; |A|=1\}|={}_{3}\mathrm{C}_{1}
$ |A|=2の場合：$ A \in \{\{1,2\},\{2,3\},\{1,3\}\}
3つの相異なるものから2つのものを選ぶ方法は$ {}_{3}\mathrm{C}_{2}通り
よって$ |\{A\in\mathfrak{P}(X_{3}) ; |A|=2\}|={}_{3}\mathrm{C}_{2}
$ |A|=3の場合：$ A =\{1,2,3\}
3つの相異なるものから3つのものを選ぶ方法は$ {}_{3}\mathrm{C}_{3}通り
よって$ |\{A\in\mathfrak{P}(X_{3}) ; |A|=3\}|={}_{3}\mathrm{C}_{3}
したがって（一般の$ nに対して書く際は分解を具体的に書かなくても良いですが、今は例を扱っているため丁寧に書くと）
$ \begin{aligned}\mathfrak{P}(X_{3})&=\{\emptyset\}\sqcup \{\{1\},\{2\},\{3\}\} \sqcup \{\{1,2\},\{2,3\},\{1,3\}\} \sqcup \{\{1,2,3\}\} \\ &=\bigsqcup_{m=0}^{3}\{A\in\mathfrak{P}(X_{3}) ; |A|=m\}\end{aligned}
となり（$ |A\sqcup B|=|A|+|B|に注意して）
$ |\mathfrak{P}(X_{3})|=\sum_{m=0}^{3}|\{A\in\mathfrak{P}(X_{3}) ; |A|=m\}|=\sum_{m=0}^{3}{}_{3}\mathrm{C}_{m}
を得ます。最後の和は二項定理の具体例$ \sum_{m=0}^{3}{}_{3}\mathrm{C}_{m}x^{m}=(1+x)^{3}で$ x=1とおけば$ 2^{3}になることが分かります 以上の例における$ 3を$ nに変えて全体を良い感じに書き直すと、一般の場合の証明になります